1. Field of the Invention
This invention relates to an improved spanning tree algorithm for use in communications networks. The invention also relates to a communications network incorporating an improved spanning tree algorithm and a computer program for controlling such a communications network.
2. Description of the Prior Art
A local area network (PLAN) is a communications network which typically covers a relatively small geographical area as compared to a wide area network (WAN). For example, a pure ether net is a type of PLAN in which two adjacent network elements may not be separated by more than about 100 m. In a PLAN, such as an ether net, messages are broadcast by a calling party and a called party decides whether to accept these broadcast messages. This differs considerably from a WAN, in which point to point connections are set up rather than broadcasting messages. Also, in a PLAN such as a pure ether net, it is possible for two or more network elements to broadcast messages simultaneously. In this situation a collision occurs and the elements can be arranged to stop broadcasting, wait for an arbitrary time and then restart the broadcast. Alternatively, the network can be made more complex by adding switches which incorporate buffers. By using buffers collisions can be avoided. In contrast, because a WAN uses point to point connections, collisions do not occur. A WAN may be used to connect two or more LANs together over long distances. Typically LANs and WANs use different types of hardware and communications protocols.
As a PLAN becomes more complex it can incorporate bridges which connect together different parts of a PLAN. However, as soon as two or more bridges are incorporated into a PLAN there is a possibility of loops existing in the network. In a PLAN such as an ether net loops are problematic because broadcast messages or packets can end up simply circulating round a loop and never reach their required destination. For a WAN, where point to point connections are used between routers this problem does not exist. The spanning tree algorithm and protocol is an ANSI/IEEE standard method that is used in networks of ether net bridges and switches to prevent infinite packet looping. This spanning tree algorithm and protocol is defined in ANSI/IEEE std 802.1D, 1993 edition. This algorithm works by breaking any loops in the communications network until it becomes a tree structure. In the event of a failure at some point in the communications network it may be possible to restore connectivity by re-running the spanning tree algorithm and making use of a previously redundant route. However, one major problem with the spanning tree algorithm is that it takes as long as twenty seconds or more to take effect. The more complex the network, the longer it will take for the spanning tree algorithm to take effect. Whilst this can be acceptable for simple ether net data networks for more complex networks it presents a problem.
An example of a WAN is a public switched telephone network. In this type of network, use of point to point connections with dial up access is advantageous because these connections are dedicated. However, for other applications such as data communications, traffic is bursty unlike telephone traffic. If dedicated connections are used for data traffic this is wasteful of resources because of the non-continuous nature of the traffic. The dedicated connections tie up resources and do not allow these to be shared. PLAN protocols, such as ether net protocol allow network resources to be shared and so do not have this disadvantage.
Another example of a WAN is a Synchronous Digital Hierarchy network (SDH). This type of network was largely designed for telephony but it can also be used for data communications. Optical fibres are used in the SDH network which provides vastly improved resources and performance (e.g. transmission of 2 mega bits per second) as compared to an ether net. The SDH network typically comprises the xe2x80x9cbackbonexe2x80x9d of a wider communications network and in the case of a protected SDH network the SDH component is formed as at least one ring. This means that if there is a fault in the SDH ring, information can be sent the other way around the ring in order to reach its destination. The ring structure allows full duplication of information by allowing information to be sent both ways around the ring.
In the situation that data switching is incorporated in a wide area telecommunications network it is advantageous to use a local area network protocol such as ether net which allows network resources to be shared. However, this introduces a problem with respect to loops in the network and the possibility of infinite packet looping. If the known spanning tree algorithm is used to prevent infinite packet looping this is problematic, because the spanning tree algorithm takes a relatively long time (e.g. 20 seconds) to complete (as compared to 50 milli seconds for correction to take place in a protected SDH network).
Another problem is that when a fault occurs in the wide area network, then it takes a relatively long time (e.g. 20 seconds) for the spanning tree algorithm to take effect to restore connectivity by removing a break on a previously redundant route.
Entities within a communications network such as an ether net each have an identifying address such as a media access control (MAC) address. Information that is being transferred from A to B within the ether net is forwarded along a path from A to B via intermediate nodes in the network. These intermediate nodes, switches or bridges receive the information and forward it on by making use of a look-up table. Each node has its own look-up table which provides information about which of the nodes outputs to send out the received information on, given information about the destination of the information (e.g. the destination MAC address). Once a spanning tree algorithm has taken effect, it is necessary to update these look-up tables because the configuration of the network has changed. Because this is difficult to effect quickly problems can arise as a result of switches forwarding information along paths that are no longer operational.
It is accordingly an object of the present invention to provide an improved spanning tree algorithm for use in communications networks which overcomes or at least mitigates one or more of the problems noted above.
According to a first aspect of the present invention there is provided a method of preventing looping of user broadcast messages in a communications network, said communications network comprising a plurality of nodes, each node having two ports, said ports being connected by links to form a ring of nodes, said method comprising the steps of:
(i) sending control signals between nodes in said communications network, each control signal comprising information about which node the control signal originated from and how many nodes have been passed in the ring since that control signal originated;
(ii) blocking one of the ports on a node to user broadcast messages if control signals received by two ports on that node are identical; and
(iii) blocking a port to user broadcast messages if identical control signals are simultaneously output from and input to that port; such that in use said ring of nodes is effectively a tree structure for the propagation of user broadcast messages and looping of user broadcast messages around the ring is prevented.
A corresponding computer program stored on a computer readable medium is provided said computer program being for controlling a communications network comprising a plurality of nodes, each node having two ports, said ports being connected by links to form a ring of nodes, said computer program being arranged to control said communications network such that:
(i) control signals are sent between nodes in said communications network, each control signal comprising information about which node the control signal originated from and how many nodes have been passed in the ring since that control signal originated;
(ii) one of the ports on a node is blocked to user broadcast messages if control signals received by two ports on that node are identical; and
(iii) a port is blocked to user broadcast messages if identical control signals are simultaneously output from and input to that port; such that in use said ring of nodes is effectively a tree structure for the propagation of user broadcast messages and looping of user broadcast messages around the ring is prevented.
A corresponding communications network is provided, said communications network comprising a plurality of nodes, each node having two ports, said ports being connected by links to form a ring of nodes, wherein:
(i) said nodes are arranged to send control signals via said links, each control signal comprising information about which node the control signal originated from and how many nodes have been passed in the ring since that control signal originated;
(ii) said ports are arranged to be blocked to user broadcast messages if control signals received by two ports on a node are identical; and
(iii) said ports are also arranged to be blocked to user broadcast messages if identical control signals are simultaneously output from and input to a port; such that in use said ring of nodes is effectively a tree structure for the propagation of user broadcast messages and looping of user broadcast messages around the ring is prevented.
This provides the advantage that a ring or loop of nodes in a communications network effectively becomes a tree structure from the point of view of the propagation of user broadcast messages in the communications network. This prevents looping of the user broadcast messages around the ring. The method of achieving this is greatly simplified as compared to the known spanning tree algorithm and thus takes effect more quickly.
Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.